﻿// 链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
struct Node {
    int data;       // 数据域
    Node* next;     // 指针域，指向下一个节点

    // 构造函数
	Node(int val) : data(val), next(nullptr) {}//: Node(int val) : data(val), next(nullptr) {} // 初始化数据和指针
};
//nullptr == null或者0
class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    // 在链表头部插入节点
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
     
        newNode->next = head;//将head复制给next,就变成这个Node对象里Next的对象
        head = newNode;//new node复制给 head
    }

    // 在链表尾部插入节点
    void insertAtTail(int val) {
        Node* newNode = new Node(val);

        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // 删除节点
    void deleteNode(int val) {
        if (head == nullptr) return;

        if (head->data == val) {
            
            Node* temp = head;//赋值给临时节点
            head = head->next;//将head下子节点复制给父节点
            delete temp;//删除临时节点
            return;
        }

        Node* curr = head;
        while (curr->next != nullptr && curr->next->data != val) {//一直便利查找下一节点的值，直到匹配上
            curr = curr->next;
        }

        if (curr->next != nullptr) {
            Node* temp = curr->next;//将next赋值给赋值给临时节点
            curr->next = curr->next->next;//再将子节点的节点赋值给当前节点，和上面只有一层的删除一样
            delete temp;
        }
    }

    // 查找节点
    bool search(int val) {
        Node* curr = head;
        while (curr != nullptr) {
            if (curr->data == val) {
                return true;
            }
            curr = curr->next;
        }
        return false;
    }

    // 打印链表
    void printList() {
        Node* curr = head;
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "nullptr" << endl;
    }

    // 析构函数，释放内存
    ~LinkedList() {
        Node* curr = head;
        while (curr != nullptr) {
            Node* next = curr->next;
            delete curr;
            curr = next;
        }
    }
};
int main()
{
    LinkedList list;

    // 插入元素
    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);
    list.insertAtTail(4);
    list.insertAtTail(5);

    // 打印链表: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
    list.printList();

    // 删除元素
    list.deleteNode(3);

    // 打印链表: 1 -> 2 -> 4 -> 5 -> nullptr
    list.printList();

    // 查找元素
    cout << "Is 4 in the list? " << (list.search(4) ? "Yes" : "No") << endl;
    cout << "Is 3 in the list? " << (list.search(3) ? "Yes" : "No") << endl;

    return 0;
}

